package top.truism.stack;

/**
 * 汉诺塔问题
 * 元素从左移动到右必须经过中间
 *
 */
public class HanoiProblem {

    public static int hanoi(int num, String left, String mid, String right) {
        if(num <= 0) {
            return 0;
        }
        // 将元素从左边全部移动到右边
        return process(num, left, mid, right, left, right);
    }

    private static int process(int num, String left, String mid, String right, String from, String to) {
        if(num == 1) {
            if(processMid(from, mid, to)) {
                print(1, from, to);
                return 1;
            }else {
                print(1, from, mid);
                print(1, mid, to);
                return 2;
            }
        }
        if(processMid(from, mid, to)) {
            String another = from.equals(left) || to.equals(left) ? right : left;
            int part1 = process(num-1, left, mid, right, from, another);
            int part2 = 1;
            print(num, from, to);
            int part3 = process(num-1, left, mid, right, another, to);
            return part1 + part2 + part3;
        }else {
            int part1 =  process(num-1, left, mid, right, from, to);
            int part2 = 1;
            print(num, from, mid);
            int part3 = process(num-1, left, mid, right, to, from);
            int part4 = 1;
            print(num, mid, to);
            int part5 = process(num-1, left, mid, right, from, to);
            return part1 + part2 + part3 + part4 + part5;
        }

    }

    private static boolean processMid(String from, String mid, String to) {
        return from.equals(mid) || to.equals(mid);
    }

    private static void print(int num, String from, String to) {
        System.out.println("Move " + num + " from " + from + " to " + to);
    }

}
